package demo1;

/**
 * 斐波那契数列模型
 *      最小花费爬楼梯 746
 */
public class test3 {
    // 以 i 位置为结尾
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }

    // 以 i 位置为起始
    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];
        for (int i = n-3; i >= 0 ; i--) {
            dp[i] = Math.min(dp[i+1], dp[i+2]) + cost[i];
        }
        return Math.min(dp[0], dp[1]);
    }
}